% !TEX TS-program = pdflatex
\documentclass[10pt, a4paper]{article}

\usepackage{a4wide}
\usepackage{color}
\usepackage{amsmath,amssymb,epsfig,pstricks,xspace}
\usepackage{german,graphics}
\usepackage{dsfont}
\usepackage{amsfonts}
\usepackage{graphics, psfrag}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{enumitem} 
\usepackage{url}
\usepackage{array,dcolumn,booktabs}
\usepackage{pdflscape}
\usepackage{amsthm}
\usepackage{ulem}

\newcounter{task}
\newcommand{\task}{\stepcounter{task}\paragraph{Task \thetask~--~Solution\\}}

\usepackage{pifont}

\newcommand{\header}{
  \begin{center}
  \fbox{\parbox{11cm}{
    \begin{center}
      {\Large 4. Problem Session -- Solution\\ \vspace{0.2em}
        {\bf Secure Channels}\\ \vspace{0.7em} (Winter Term 2014/2015)\\
        \vspace{0.2em} \firstnameone \lastnameone\\
        \vspace{0.2em} \matriculationnumberone\\
        \vspace{0.2em} \firstnametwo \lastnametwo\\
        \vspace{0.2em} \matriculationnumbertwo \\
       \vspace{0.2em} \firstnamethree \lastnamethree\\
        \vspace{0.2em} \matriculationnumberthree
    }
    \end{center}
  }}
  \end{center}
}


%-------------------------------------------------------------------------------
%---------------------------- EDIT FROM HERE -----------------------------------
%-------------------------------------------------------------------------------

\newcommand{\firstnameone}{Jiaqi	}
\newcommand{\lastnameone}{Weng}
\newcommand{\matriculationnumberone}{115131}

\newcommand{\firstnametwo}{Vasilii	}
\newcommand{\lastnametwo}{Ponteleev}
\newcommand{\matriculationnumbertwo}{115151}

\newcommand{\firstnamethree}{Naveeni	}
\newcommand{\lastnamethree}{ Kumar Goswam}
\newcommand{\matriculationnumberthree}{113967}

\begin{document}
\pagestyle{plain}
\header


% number of tasks are automatically generated

\task
a) Test if  polynomial is irreducible
\\\\1) $f_1(x)$ = $x^2 + 1$ with F = $Z_2$ 
\\$f_1(x) = 0 \Leftrightarrow x^2 + 1 = 0$
\\$x^2 = 1$
\\$x_1 = 1$, $x_2 = 1$
\\Thus, $f_1(x) = x^2 + 1 = (x + 1)(x+1)$ - reducible polynomial
\\\\2) $f_2(x)$ = $x^2 + x + 1$ with F = $Z_2$
\\$f_2(x) = 0 \Leftrightarrow x^2 + x + 1 = 0$
\\$x^2 + x = 1$
\\$x(x + 1) = 1$
\\$x = 1$ and $x + 1 = 1$
\\$x = 1$ and $x = 0, \Rightarrow $ no solution exists
\\Thus, $f_2(x) = x^2 + x + 1$ - irreducible polynomial
\\\\3) $f_3(x)$ = $x^4 + 2x^2 + x$ with F = $Z_3$ 
\\Since $x^4 + 2x^2 + x$  = $x(x^3 + 2x + 1)$ $f_3$ is reducible polynomial
\\\\b)
\\Finite field $GF(2^3)$ over $p(x) = x^3 + x + 1$


\begin{center}
    \begin{tabular}{ | p{1.4cm} | p{1.4cm} | p{1.4cm} | p{1.4cm} |  p{1.4cm} |  p{1.4cm} |  p{1.4cm} |  p{1.4cm} |  p{1.4cm} |}
    \hline
   \boldmath{$+$} & \boldmath{$0$} & \boldmath{$1$} & \boldmath{$x$} & \boldmath{$x + 1$} & \boldmath{$x^2$} & \boldmath{$ x^2 + 1$} & \boldmath{$x^2 + x$} & \boldmath{$x^2 + x + 1$} \\ \hline

    \boldmath{$0$} & $0$ & $1$ & $x$ & $x + 1$ & $x^2$ & $x^2 + 1$ & $x^2 + x$ & $x^2 + x + 1$ \\ \hline

    \boldmath{$1$} & $1$ & $0$ & $x + 1$ & $x$ & $x^2 + 1$ & $x^2$ & $x^2 + x + 1$ & $x^2 + x$ \\ \hline

    \boldmath{$x$} & $x$ & $x + 1$ & $0$ & $1$ & $x^2 + x$ & $x^2 + x + 1$ & $x^2$ & $x^2 + 1$ \\ \hline

    \boldmath{$x + 1$}  & $x + 1$ & $x$ & $1$ & $0$ & $x^2 + x + 1$ & $x^2 + x$ & $x^2 + 1$ & $x^2$ \\ \hline

    \boldmath{ $x^2$} & $x^2$  & $x^2 + 1$ & $x^2 + x$ & $x^2 + x + 1$ & $0$ & $1$ & $x$ & $x + 1$ \\ \hline

    \boldmath{$x^2 + 1$} & $x^2 + 1$ & $x^2$ & $x^2 + x + 1$ & $x^2 + x$ & $1$ & $0$ & $x + 1$ & $x$ \\ \hline

    \boldmath{$x^2 + x$} & $x^2 + x$ & $x^2 + x + 1$ & $x^2$ & $x^2 + 1$ & $x$ & $x + 1$ & $0$ & $1$ \\ \hline

    \boldmath{$x^2 + x + 1$} & $x^2 + x + 1$ & $x^2 + x$ & $x^2 + 1$ & $x^2$ & $x + 1$ & $x$ & $1$ & $0$ \\ \hline

    \hline
    \end{tabular}
\end{center}



\begin{center}
    \begin{tabular}{ | p{1.4cm} | p{1.4cm} | p{1.4cm} | p{1.4cm} |  p{1.4cm} |  p{1.4cm} |  p{1.4cm} |  p{1.4cm} |  p{1.4cm} |}
    \hline
   \boldmath{$*$} & \boldmath{$0$} & \boldmath{$1$} & \boldmath{$x$} & \boldmath{$x + 1$} & \boldmath{$x^2$} & \boldmath{$ x^2 + 1$} & \boldmath{$x^2 + x$} & \boldmath{$x^2 + x + 1$} \\ \hline

    \boldmath{$0$} & $0$ & $0$ & $0$ & $0$ & $0$ & $0$ & $0$ & $0$ \\ \hline

    \boldmath{$1$} & $0$ & $1$ & $x$ & $x + 1$ & $x^2$ & $x^2 + 1$ & $x^2 + x$ & $x^2 + x + 1$ \\ \hline

    \boldmath{$x$} & $0$ & $x$ & $x^2$ & $x^2 + x$ & $x + 1$ & $1$ & $x^2 + x + 1$ & $x^2 + 1$ \\ \hline

    \boldmath{$x + 1$}  & $0$ & $x + 1$ & $x^2 + x$ & $x^2 + 1$ & $x^2 + x + 1$ & $x^2$ & $1$ & $x$ \\ \hline

    \boldmath{ $x^2$} & $0$ & $x^2$ & $x + 1$ & $x^2 + x + 1$ & $x^2 + x$ & $x$ & $x^2 + 1$ & $1$ \\ \hline

    \boldmath{$x^2 + 1$} & $0$ & $x^2 + 1$ & $1$ & $x^2$ & $x$ & $x^2 + x + 1$ & $x + 1$ & $x^2 + x$ \\ \hline

    \boldmath{$x^2 + x$} & $0$ & $x^2 + x$ & $x^2 + x + 1$ & $1$ & $x^2 + 1$ & $x + 1$ & $x$ & $x^2$ \\ \hline

    \boldmath{$x^2 + x + 1$} & $0$ & $x^2 + x + 1$ & $x^2 + 1$ & $x$ & $1$ & $x^2 + x$ & $x^2$ & $x + 1$ \\ \hline

    \hline
    \end{tabular}
\end{center}
c)
\\There are not so many polynomials of degree 2 with coefficients from $Z_2$ apart from $x^2 + x + 1$:
\\1) $x^2 + x$ = $x(x + 1)$,
\\2) $x^2 + 1$ = $(x + 1)(x + 1)$ as was demonstrated above,
\\3) $x^2$ = $xx$.
\\Thus, $x^2 + x + 1$ is the only irreducible polynomial of degree 2 with coefficients from $Z_2$.
\\\\d)
\\Inverse proof. Assume that there exists such a from field F for which $p(a) = 0$. 
\\It means that there esixt polymomial q(x) of degree less than p(x), and $p(x) = q(x)(x - a)$ holds, which means p(x) has at least 2 divisors with degrees more than 0, and, thus, riducible.

\task
Choose $M1$ as 0 $\Rightarrow$ C1 will be Ek(0)= K\\
Choose M2 as K  $\Rightarrow$ C2 = Ek ( K$\oplus$ K ) $\Rightarrow$ Ek(0) $\Rightarrow$ K\\
Tag will be T== Ek(k) $\Rightarrow$ S\\\\
Choose $M1^{'}$ as K $\Rightarrow$ $C1^{'}$ will be Ek(k)$ \Rightarrow$ S\\
Choose $M2^{'}$ as S $\Rightarrow$ $C2^{'}$ = $Ek( S \oplus S )$ $\Rightarrow$ Ek(0) $\Rightarrow$ K\\
Now Tag $T^{'}$ = should be Ek( K) which is equal to S

\task
Choose M1 as 0 , C1= Ek(0)  $\Rightarrow$  T\\
Now Choose M2 as T and as L is 0 Tag will be\\
Tag = $Ek( T \oplus T ) == Ek(0)$ which should be equal to T.

\task
a)\\
For queries $2^{b/2}$ of values of Yi\\
The pr[Yi=Yj, i is not equal to j] is approximately $\simeq$ 0.36 ( Birthday Bound) (1)\\\\
for i=0 tp i = q\\
ask for (Mi, Ti)\\\\
Check if Ti=Tj( which should be equal with probability of  $\simeq$  0.36 according to (1)\\
Well this is also the advantage of the adversary if it allows to make $2^{b/2}$ queries.\\\\
b)\\
Choose m1 as T and m2 also as T the resulting why y1 and y2 will be Ek(T) and
Ek(T). $Y = Y1 \oplus Y1  \Rightarrow  Ek(T) \oplus Ek(T) \Rightarrow  0$\\\\
Now Choose $m1^{'}$ as S and $m2^{'}$ as S the resulting Y will also be 0.
This is very clear that two different message will result in the same Tag as both message's Y
value will turn up as 0 while producing Tag. which would result in producing same tag

\task
Consists of 2 files:
\\1) GF.py - library source code
\\2) 115131.py - unit tests.
\\\\To run tests simply execute file 115131.py. Tests cover pretty much all functionality.
Works for both Python 2.7.* and Python 3.*.



\end{document}
